package com.leetcode;

import java.util.Arrays;

public class TestOnePivotSort {

	public static void main(String[] arg0) {
		int[] test = new int[] { 30, 21, 19, 29, 45, 25, 7, 25, 22, 2, 22, 24, 77, 25, 63 };
		int pivot = test[7];
		int less = 0;
		int great = 14;
		// less 始终会小于等于k，而且一次循环less的增量始终是0或1
		// great 在一次循环的减少可能是0，可能是1，可能是很多
		for (int k = less; k <= great; ++k) {
			System.out.println("k = " + k);
			if (test[k] == pivot) {
				continue;
			}
			int ak = test[k];
			if (ak < pivot) {
				test[k] = test[less];
				test[less] = ak;
				++less;
				System.out.println("less = " + less);
			} else { // ak > pivot
				while (test[great] > pivot) {
					--great;
					System.out.println("> great = " + great);
				}
				if(test[great] < pivot) {
					test[k] = test[less];
					test[less] = test[great];
					++less;
					System.out.println("< less = " + less);
				} else { // test[great] == pivot
					test[k] = pivot;
				}
				test[great] = ak;
				--great;
				System.out.println("great = " + great);
			}
		}
		System.out.println("单轴分区后的数组  = " + Arrays.toString(test));
	}

}
